import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 优先级队列的模拟实现
 */
public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap() {
        this.elem = new int[10];
    }
    /**
     * 初始化数组
     */
    public void initHeap(int[] array) {
        for(int i = 0;i < elem.length;i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    /**
     * 构建大根堆
     */
    public void createBigHeap() {
        int parent = (usedSize - 1 - 1) / 2;
        for(int i = parent;i >= 0;i--) {
            siftDown(i,usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent
     * @param len
     */
    private void siftDown(int parent,int len) {
        int child = 2 * parent + 1;
        while(child < len) {
            if(child + 1 < len
                    && elem[child] <  elem[child + 1]) {
                child++;
            }
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
    private void swap(int i,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    /**
     *插入元素
     *  1.判断是否为满
     *  2.插入usedSize位置
     *  3.向上调整
     */
    public void offer(int val) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        elem[usedSize] = val;
        int parent = (usedSize - 1) / 2;
        usedSize++;
        siftUp(parent);
    }

    /**
     * 判满
     * @return
     */
    private boolean isFull() {
        return elem.length == usedSize;
    }
    /**
     * 向上调整
     *  1.判断是否大于根节点,大于交换
     *  2.一直交换,直到child<0
     */
    public void siftUp(int parent) {
        int child = usedSize - 1;
        while(parent >= 0 ) {
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
    /**
     * 删除元素
     */
    public int poll() {
        int tmp = elem[0];
        swap(0,usedSize - 1);
        usedSize--;
        siftDown(0,usedSize - 1);
        return tmp;
    }
    /**
     * 堆排序
     *      1.变成大根堆
     *      2.0,usedSize -1交换
     *      3.向下调整
     */
    public void heapSort() {
        int end = usedSize - 1;
        while(end > 0 ) {
            swap(0,end);
            siftDown(0,end);
            end--;
        }
    }
    /**
     最小K个数
     方法一:
     1.创建小根堆(而默认就是小根堆PriorityQueue)
     2.弹出前k个元素
     */
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i = 0;i < arr.length;i++) {
            priorityQueue.offer(arr[i]);
        }

        for(int i = 0;i< k;i++) {
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }
    /**
     最小K个数
     方法二:
     1.创建只有k个元素的大根堆(传比较器)
     2.遍历k以后得元素,小于交换,大于忽略
     3.弹出前k个元素
     */
    public int[] smallestK2(int[] arr, int k) {
        int[] ret = new int[k];
        if(k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Cmp2());
        for(int i = 0;i < k;i++) {
            priorityQueue.offer(arr[i]);
        }
        for(int i = k;i < arr.length;i++) {
            int tmp = priorityQueue.peek();
            if(tmp > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for(int i = 0;i < k;i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}
class Cmp2 implements Comparator<Integer> {
    public int compare(Integer o1,Integer o2) {
        return o2 - o1;
    }
}

